package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 10- II. 青蛙跳台阶问题 https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 */
public class NumWays {

    public int numWays(int n) {
        if(n == 0) return 1;
        if(n <= 2) return n;
        int dpi_2 = 1, dpi_1 = 2, dpi = 3;
        for(int i = 3;i <= n;i++) {
            dpi = (dpi_1 + dpi_2) % 1000000007;
            dpi_2 = dpi_1;
            dpi_1 = dpi;
        }
        return dpi;
    }
}
